package leetcode.code1605;

import java.util.Arrays;

public class Solution {
	public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
		int m = rowSum.length, n = colSum.length;
		int[][] ans = new int[m][n];
		Integer[] row = new Integer[m];
		Integer[] col = new Integer[n];
		for (int i = 0; i < m; i++) {
			row[i] = i;
		}
		for (int i = 0; i < n; i++) {
			col[i] = i;
		}
		Arrays.sort(row, (a, b) -> rowSum[a] - rowSum[b]);
		for (int i = 0; i < m; i++) {
			int x = row[i], sum = rowSum[x];
			Arrays.sort(col, (a, b) -> colSum[a] - colSum[b]);
			for (int j = 0; j < n && sum > 0; j++) {
				if (colSum[col[j]] != 0) {
					int num = Math.min(sum, colSum[col[j]]);
					ans[x][col[j]] = num;
					colSum[col[j]] -= num;
					sum -= num;
				}
			}
		}
		return ans;
	}
}
